package algorithm.dynamic;

import java.util.ArrayList;
import java.util.List;

/**
 * @author bingo
 * @Description  走楼梯问题
 * @Date 2018/6/19
 */
public class GoStairs {

    private static List<Integer> numberList = new ArrayList<>();


    public static  int  goStairs2(int n){
        if(n==1){
            return  1;

        }
        if(n==2){

            return 2;
        }
        if(numberList.get(n)==-1){
            numberList.set(n,goStairs2(n-1)+goStairs2(n-2));
        }

        return   numberList.get(n);

    }



    public  static  int  goStairs(int n){
        Integer[] a = new Integer[n+1];
        a[1] = 1;
        a[2] = 2;
        for(int i=3;i<=n;i++){
            a[i] = a[i-1]+a[i-2];
        }

        return a[n];
    }
    public  static  int  goStairs3(int n){
        Integer[] a = new Integer[n+1];
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        a[4] = 6;
        a[5] = 12;
        for(int i=6;i<=n;i++){
            a[i] = a[i-1]+a[i-2]+a[i-3]+a[i-4]+a[i-5];
        }

        return a[n];
    }

    public static  int  goStairs4(int n){
        if(n==1){
            return  1;

        }
        if(n==2){

            return 2;
        }
        if(n==3){
           return  4;

        }
        if(n==4){

            return 8;
        }
        if(n==5){
            return  16;

        }

        if(numberList.get(n)==-1){
            numberList.set(n,goStairs4(n-1)+goStairs4(n-2)+goStairs4(n-3)+goStairs4(n-4)+goStairs4(n-5));
        }

        return   numberList.get(n);

    }


    public static void main(String[] args) {

      int n=45;
        for(int i=0;i<n+1;i++){
            numberList.add(i,-1);
        }
       // System.out.println(GoStairs.goStairs2(10));
        //System.out.println(GoStairs.goStairs(10));
        System.out.println(GoStairs.goStairs4(10));
    }
}
